Sieve of Eratosthenes


To find Prime Numbers between 1 and 100

OVERVIEW


The Sieve of Eratosthenes is a highly efficient algorithm for finding all prime numbers up to a given number N. Instead of checking each number individually, it eliminates multiples of primes systematically, reducing unnecessary calculations. The algorithm runs in O(N log log N) time, making it much faster than basic methods like trial division.

Working


  • Start with a list of numbers from 1 to N and assume all are prime.
  • Mark multiples of each prime as non-prime, starting from 2.
  • Continue the process for numbers up to √N, leaving only prime numbers unmarked.


Color Representation


  • Grey → Prime Numbers.
  • Aqua → Non-Prime.
  • Pink → Processing.